package base.sort;

import base.utils.ArrayUitls;
import base.utils.PrintUtils;

import java.util.Arrays;

/**
 * 堆排序
 * https://www.runoob.com/w3cnote/heap-sort.html
 *
 * 将最大/最小值 ， 放入到 堆的顶部，然后将其移除(记录下最值) ， 再次重新建立顶堆
 *
 */
public class HeapSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        int len = arr.length;

        buildMaxHeap(arr, len);
        PrintUtils.print(ArrayUitls.arr2String(arr));

        for (int i = len - 1; i > 0; i--) {
            swap(arr, 0, i);                    // 将最大值，移动到 最右边，
            len--;
            heapify(arr, 0, len);
        }
        return arr;
    }

    //

    /**
     * 建立大顶堆
     *  // 这里从 len / 2 开始建立，left =  2 * i + 1; 在这个从(len / 2)  ---> 0  的过程中，这里 从i = len / 2 开始，
     *  是因为 2 + 2^2 + 2^3 + 2^4  + .... + 2^n = 2^(n+1) - 2  ,
     *  将从结点树的倒数第二层开始，其
     * @param arr
     * @param len
     */
    private void buildMaxHeap(int[] arr, int len) {
        for (int i = len / 2; i >= 0; i--) {
            heapify(arr, i, len);
        }
    }

    /**
     * 因为 heapify递归的原因，所以他会将 这个 指定的数组中最大值，提到 堆的顶部。
     * @param arr 需要对处理的数组
     * @param i   堆的顶点
     * @param len 堆的结束的
     */
    private void heapify(int[] arr, int i, int len) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largest = i;                    // 使用largest记录下 ， 不符合大顶堆的坐标

        if (left < len && arr[left] > arr[largest]) {
            largest = left;
        }

        if (right < len && arr[right] > arr[largest]) {
            largest = right;
        }

        //
        if (largest != i) {
            swap(arr, i, largest);
            heapify(arr, largest, len);
        }
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }


}
